package tree;

import java.util.*;

/**
 * @author kaho
 * @since 2021/2/26
 */
public class _116_填充每个节点的下一个右侧节点指针 {

    /**
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     *
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     *
     * 初始状态下，所有 next 指针都被设置为 NULL。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param root
     * @return
     */
    public static Node connect2(Node root){
        dfs1(root);
        return root;
    }

    private static void dfs1(Node root) {
        if (root == null) {
            return;
        }
        Node left = root.left;
        Node right = root.right;
        while (left!=null) {
            left.next = right;
            left = left.right;
            right = right.left;
        }
        dfs1(root.left);
        dfs1(root.right);
    }



    public static Node connect1(Node root) {
        dfs(root);
        return root;
    }

    private static void dfs(Node root) {
        if (root == null) {
            return;
        }
        Node left = root.left;
        Node right = root.right;
        while (left != null) {
            left.next = right;
            left = left.right;
            right = right.left;
        }
        dfs(root.left);
        dfs(root.right);
    }


    public static Node connect(Node root) {
        if (root == null) {
            return null;
        }

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node poll = queue.get(0);
            for (int i = 1; i < size; i++) {
                Node next = queue.get(i);
                poll.next = next;
                poll = next;
            }

            for (int i = 0; i < size; i++) {
                Node poll1 = queue.remove();
                if (poll1.left!=null) {
                    queue.add(poll1.left);
                }
                if (poll1.right!=null) {
                    queue.add(poll1.right);
                }
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        Node connect = connect(n1);
    }
}
